Employee importance [DFS, BFS]

Time: O(N); Space: O(H); easy

You are given a data structure of employee information, which includes the employee’s unique id, his importance value and his direct subordinates’ id.

For example: * employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. * They have importance value 15, 10 and 5, respectively. * Then employee 1 has a data structure like [1, 15, [2]], and employee 2 has [2, 10, [3]], and employee 3 has [3, 5, []]. * Note that although employee 3 is also a subordinate of employee 1, the relationship is not direct.

Now given the employee information of a company, and an employee id, you need to return the total importance value of this employee and all his subordinates.

Example 1:

Input: employees =

[
    [1, 5, [2, 3]],
    [2, 3, []],
    [3, 3, []]
],
id = 1

Output: 11

Explanation:

• Employee 1 has importance value 5, and he has two direct subordinates: employee 2 and employee 3.

• They both have importance value 3.

• So the total importance value of employee 1 is: 5 + 3 + 3 = 11.

Example 2:

Input: employees =

[
    [1, 2, [2]],
    [2, 3, []]
],
id = 2

Output: 3

Explanation:

• The total importance value of employee 1 is 3

Notes:

• One employee has at most one direct leader and may have several subordinates.

• The maximum number of employees won’t exceed 2000.

class Employee(object):
    """
    Employee info
    """
    def __init__(self, id, importance, subordinates):
        # It's the unique id of each node; unique id of this employee
        self.id = id
        # the importance value of this employee
        self.importance = importance
        # the id of direct subordinates
        self.subordinates = subordinates

    def __iter__(self):
        self.__i = 0                #  iterable current item
        return iter(self.subordinates)

    def __next__(self):
        if self.__i < len(self.subordinates) - 1:
            self.__i += 1
            return self.subordinates[self.__i]
        else:
            raise StopIteration

1. Depth-First Search

Intuition and Algorithm

Let’s use a hashmap emap = {employee.id -> employee} to query employees quickly.

Now to find the total importance of an employee, it will be the importance of that employee, plus the total importance of each of that employee’s subordinates.

This is a straightforward depth-first search.

class Solution1(object):
    """
    Time: O(N), where N is the number of employees. We might query each employee in DFS.
    Space: O(N), the size of the implicit call stack when evaluating DFS.
    """
    def getImportance(self, employees, query_id):
        """
        :type employees: List[Employee]
        :type id: int
        :rtype: int
        """
        emap = {e.id: e for e in employees}

        def dfs(eid):
            employee = emap[eid]
            return (employee.importance +
                    sum(dfs(emp_obj.id) for emp_obj in employee.subordinates))
        return dfs(query_id)

s = Solution1()

employee3 = Employee(3, 3, [])
employee2 = Employee(2, 3, [])
# Attn: use objects in subordinates
employee1 = Employee(1, 5, [employee2, employee3])
id = 1
employees = [employee1, employee2, employee3]
assert s.getImportance(employees, id) == 11

class Solution2(object):
    """
    Time: O(N)
    Space: O(H)
    """
    def getImportance(self, employees, id):
        """
        :type employees: Employee
        :type id: int
        :rtype: int
        """
        if employees[id-1] is None:
            return 0

        result = employees[id-1].importance

        for id in employees[id-1].subordinates:
            result += self.getImportance(employees, id)

        return result

s = Solution2()

employee3 = Employee(3, 3, [])
employee2 = Employee(2, 3, [])
employee1 = Employee(1, 5, [2, 3])
id = 1
employees = [employee1, employee2, employee3]
assert s.getImportance(employees, id) == 11

import collections

class Solution3(object):
    def getImportance(self, employees, id):
        """
        :type employees: Employee
        :type id: int
        :rtype: int
        """
        result, q = 0, collections.deque([id])
        while q:
            curr = q.popleft()
            employee = employees[curr-1]
            result += employee.importance
            for id in employee.subordinates:
                q.append(id)
        return result

s = Solution3()

employee3 = Employee(3, 3, [])
employee2 = Employee(2, 3, [])
employee1 = Employee(1, 5, [2, 3])
id = 1
employees = [employee1, employee2, employee3]
assert s.getImportance(employees, id) == 11

See also:

https://leetcode.com/problems/employee-importance

https://www.lintcode.com/problem/employee-importance/description

Related problems:

https://leetcode.com/problems/nested-list-weight-sum/